package Leetcode第二期;

import java.util.Arrays;

/**
 * @author : K k
 * @date : 10:34 2020/10/16
 * 给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：[-4,-1,0,3,10]
 * 输出：[0,1,9,16,100]
 * 示例 2：
 *
 * 输入：[-7,-3,2,3,11]
 * 输出：[4,9,9,49,121]
 */
public class 有序数组的平方_977 {
    public int[] sortedSquares(int[] A) {
        for(int i=0;i<A.length;i++){
            A[i]=A[i]*A[i];
        }
        Arrays.sort(A);
        return A;
    }

    //双指针
    public int[] sortedSquaresA(int[] A) {
        int n = A.length;
        int border=-1;
        for (int i=0;i<n;i++){
            if (A[i]<0){
                //实时更新border为最后一位负数
                border=i;
            }else {
                break;
            }
        }
        int[] ans = new int[n];
        int index=0,i=border,j=border+1;
        while (i >= 0 || j < n) {
            if (i<0){
                //全为正数
                ans[index]=A[j]*A[j];
                ++j;
            }else if (j==n){
                //全为负数 颠倒
                ans[index]=A[i]*A[i];
                --i;
            }else if (A[i]*A[i]<A[j]*A[j]){
                //扩散比较
                ans[index]=A[i]*A[i];
                i--;
            }else {
                ans[index]=A[j]*A[j];
                j++;
            }
            index++;
        }
        return ans;
    }

}
